package com.lry.basic.algorithm.queue;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/7/12
 */
public class PriorityQueue  {
    private int size;
    private int capacity = 10;
    private int[] queue;
    private boolean flag;//false:默认最小堆,true代表最大堆

    public PriorityQueue(boolean flag,int capacity){
        this.flag = flag;
        this.capacity = capacity;
        queue = new int[capacity];
    }
    public PriorityQueue(boolean flag){
        this.flag = flag;
        queue = new int[capacity];
    }
    //默认最小堆
    public PriorityQueue(int capacity){
        this.capacity = capacity;
        queue = new int[capacity];
    }
    //默认最小堆 默认capacity = 10;
    public PriorityQueue(){
        queue = new int[capacity];
    }

    public int dequeue(){
        if(size==0)return 0;
        int temp = queue[0];//保留 出堆的元素
        --size;
        queue[0] = queue[size];//最后一个元素赋给堆顶
        queue[size] = 0;//最后一个置为0
        //对根节点进行调整
        sift(queue,0,size-1);
        return temp;
    }
    //调整算法
    //k是待调整的节点的下标
    //m是最后一个元素的下标
    public void sift(int[] arr,int k,int m){
        int i = k;//i指向待调整的节点
        int j = 2*i+1;//j先指向左孩子
        while(j<=m){
            if(!flag){//最小堆
                if(j<m&&arr[j]>arr[j+1]){//右孩子较小，j应该指向右孩子
                    ++j;
                }
                if(arr[i]<arr[j]){//已经是最小堆了，break
                    break;
                }
            }else{//最大堆
                if(j<m&&arr[j]<arr[j+1]){//右孩子较大，j指向右孩子
                    ++j;
                }
                if(arr[i]>arr[j]){//已经是最大堆，break
                    break;
                }
            }
            swap(arr,i,j);//交换
            i=j;//继续向下调整
            j=2*i+1;
        }
    }
    public static  void swap(int[] arr, int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public int take() {
        return size==0?0:queue[0];
    }
    //入堆 不允许0
    public boolean enque(int in) {
        if(in==0)return false;
        int i = size++;//当前节点的下标
        if(i>=capacity)return false;
        while(i>0){
            int par = (i-1)/2;//父亲的下标
            //flag==false 最小堆
            //falg=true 最大堆
            if(!flag?queue[par]<=in:queue[par]>=in)break;

            queue[i] = queue[par];//把父亲的值放下来
            i = par;//自己的下标提上去
        }
        queue[i] = in;//把入堆元素放在合适的位置
        return true;
    }

    public int size() {
        return size;
    }
    public int[] getQueue(){
        return queue;
    }
}
